The present invention is directed to reducing the memory necessary to accomplish the processing of a digital image. In particular, this invention capitalizes on the need to store digitized images in a compressed format, and incorporates rotation, mirroring, and transposition operations with a JPEG (Joint Photographic Experts Group) standard compression or decompression operation so as to accomplish rotation, mirroring and transposition on compressed images in a computationally efficient manner.
Data compression is required in data handling processes, where too much data is present for practical applications using the data. Commonly, compression is used in communication links, to reduce the transmission time or required bandwidth. Similarly, compression is preferred in image storage systems, including digital printers and copiers, where "pages" of a document to be printed are stored temporarily in precollation memory. Here the amount of media space on which the image data is stored can be substantially reduced with compression. Generally speaking, scanned images, i.e., electronic representations of hard copy documents, are often large, and thus make desirable candidates for compression.
The DCT (Discrete Cosine Transform) and variable-length encoding standard, disseminated by the JPEG committee, is a lossy compression system which reduces data redundancies based on pixel to pixel correlations. Generally, an image does not change very much on a pixel to pixel basis and therefore has what is known as "natural spatial correlation". In natural scenes, correlation is generalized, but not exact. Noise makes each pixel somewhat different from its neighbors.
Generally, FIG. 1 illustrates a JPEG DCT compression and decompression system. A more complete discussion may be had by referencing the Encyclopedia of Graphics File Formats, by J. D. Murray and W. vanRyper, pp. 159-171 (1994, O'Reilly & Associates, Inc.) Further description of the JPEG standard may be found, for example, in JPEG Still Image Data Compression Standard, by W. Pennebaker and J. Mitchell, 1993 (Van Nostrand Reinhold, New York) or Discrete Cosine Transform: Algorithms, Advantages and Applications, by K. Rao and P. Yip, 1990 (Academic Press, San Diego).
Initially provided is tile or block memory 10 storing an M.times.M segment of the image. From the portion of the image stored in memory, the discrete cosine transform (DCT), a frequency space representation of the image, is formed at transformer 12. Hardware implementations of the compression engine are available, such as the C-Cube Microsystems CL550A JPEG image compression processor, which operates in either the compression or the decompression mode according to the JPEG standard. As described below, the embodiments of the present invention may include hardware and/or software processing operations. A divisor/quantization device 14 is used, from a set of values referred to as a Q-Table stored in a Q-Table memory 16, so that a distinct Q-Table value is divided into the DCT value, returning the integer portion of the value as the quantized DCT value. A Huffman encoder 18 uses statistical encoding applied to the quantized DCT values to generate the compressed image in a variable-length coded unit that is output for storage, transmission, etc.
To decompress compressed image data, and with continued reference to FIG. 1, a series of functions or steps are followed to reverse the compression process described above. The Huffman encoding is removed at decoder 20. The image signal now represents the quantized DCT coefficients, which are multiplied at signal multiplier 22 by the Q-Table values in memory 24 in a process inverse to the compression process. At inverse transformer 26, the inverse transform of the discrete cosine transform is derived, and the output image in the spatial domain is stored at image buffer 28.
As the processing of JPEG compressed images is typically accomplished in the spatial domain, such processes generally require the decompression of the image before processing and the re-compression after processing to minimize image size. An object of the present invention is to accomplish the orthogonal rotation and/or mirroring of the M.times.M blocks within a JPEG compressed image without having to completely decompress the coded units representing such blocks. The proposed invention employs a two-step process to accomplish orthogonal increment rotation or mirroring, requiring only an intermediate buffer having a storage capacity approximately on the order of the coded unit itself. Thus, for any image having a compression ratio of at least two, there is a memory savings with the processing technique of the present invention relative to accomplishing the processing in a spatial domain. Accordingly, the present invention enables the rotation and mirroring of an image by processing only the compressed data, with no a priori knowledge of the structure of the compressed image.
Heretofore, a number of patents and publications have disclosed image compression or rotation operations, the relevant portions of some may be briefly summarized as follows:
U.S. Pat. No. 5,408,425 to H. S. Hou, issued Apr. 18, 1995, hereby incorporated by reference for its teachings, discloses a processor and method of computation for performing a discrete cosine transform. PA1 U.S. Pat. No. 5,319,724 to S. M. Blonstein et al., issued Jun. 7, 1994, teaches an apparatus and corresponding method for compressing still images while remaining compatible with a JPEG transformation. PA1 U.S. Pat. No. 5,257,113 to Chen et al., issued Oct. 26, 1993, discloses a video mixing technique that employs JPEG compressed data. Windows within a video image are each represented as JPEG coded data streams. The streams are then mixed using a data structure, based upon the overlay configuration of the windows, to produce a composite frame of video information. PA1 U.S. Pat. No. 5,327,248 to Miller et al., issued Jul. 8, 1994, teaches a compressed image virtual editing system, where the compressed image is the result of JPEG compression techniques. The system enables a decoding of selected blocks in the JPEG compressed image to create a virtual image. Subsequently, the virtual image may be edited and re-encoded thereby allowing editing of the virtual image only and without decoding the entire compressed image.
In accordance with the present invention, there is provided a method for performing an image processing operation on compressed digital image data comprising a plurality of coded units, wherein each coded unit is a variable-length representation of the coefficients of a discrete cosine transform for a segment of a digital image, the method including the steps of: retrieving from a memory a coded unit; at least partially variable-length decoding the coded unit to produce a quantized coefficient matrix; processing the quantized coefficient matrix in accordance with the image processing operation to produce a processed coefficient matrix; variable-length encoding the processed coefficient matrix to produce a processed coded unit; and repeating the above steps for each of the plurality of coded units in the compressed digital image data to produce coded units of a processed, compressed image.
In accordance with another aspect of the present invention, there is provided a method for performing an image processing operation on compressed digital image data comprising a plurality of coded units, wherein each coded unit is a variable length representation of the coefficients of a discrete cosine transform for a segment of a digital image, the method including the steps of: retrieving from a memory a coded unit; variable-length decoding the coded unit to produce a quantized coefficient matrix, said decoding step further determining the size of the coded unit; storing, in memory, a pointer to each coded unit reflecting the storage location, in memory of the DC offset component for the coded unit processing the quantized coefficient matrix in accordance with the image processing operation to produce a processed matrix; dequantizing the processed matrix to produce a processed array of quantized coefficients; inverse discrete cosine transforming the processed array of quantized coefficients to produce a processed image segment; and repeating the above steps for each of the plurality of coded units in the compressed digital image data to produce a plurality of processed segments of image data.
In accordance with yet another aspect of the present invention, there is provided a method for performing an image processing operation on digital image data, including the steps of: segmenting the digital image data into blocks of data; transforming, using a discrete cosine transform, each block of data to produce DCT coefficients representative thereof; quantizing the DCT coefficients to produce a quantized DCT coefficient matrix for each block of data; processing the quantized coefficient matrix in accordance with the image processing operation to produce a processed coefficient matrix for each block of data; scanning the processed coefficient matrix in accordance with a predefined path to produce a vector of quantized coefficients for each block of data; compressing the quantized coefficient vector using variable length encoding so as to produce a processed coded unit for each block of data; and storing the plurality of coded units in memory to produce a processed, compressed image
One aspect of the invention deals with a basic problem in digital image processing systems--the memory and computationally intensive operation of image processing, particularly image rotation. This aspect is further based on the discovery of a technique that alleviates this problem. The technique accomplishes the processing of an image segment or block while in a compressed form produced by a JPEG (e.g., discrete cosine transform) compression operation.
This technique can be implemented, for example, by the modification of a basic JPEG compression engine, where rotation operations are performed on the compressed image data (coded units). Accordingly, the technique has application to any number of systems, including digital printers and copiers where there may be a necessity to orthogonally rotate the digital image. A machine implementing the invention can include a data or image processing system having the capability of JPEG compression. The techniques and system described herein are advantageous because they are efficient and result in the ability to accomplish basic image processing with little additional hardware or processing as compared to other memory intensive approaches.